home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group93c.txt / 000127_icon-group-sender _Tue Dec 14 00:16:09 1993.msg < prev    next >
Internet Message Format  |  1994-02-02  |  3KB
  1. Received: by cheltenham.cs.arizona.edu; Thu, 16 Dec 1993 23:05:50 MST
  2. Date: 14 Dec 93 00:16:09 GMT
  3. From: organpipe.uug.arizona.edu!CS.Arizona.EDU!not-for-mail@uunet.uu.net  (Nevin Liber)
  4. Organization: University of Arizona CS Department, Tucson AZ
  5. Subject: Re: Need help with (simple?) programming problem.
  6. Message-Id: <2ej0k9$5jg@caslon.CS.Arizona.EDU>
  7. References: <rfgCHyt15.Fpz@netcom.com>
  8. Sender: icon-group-request@cs.arizona.edu
  9. To: icon-group@cs.arizona.edu
  10. Status: R
  11. Errors-To: icon-group-errors@cs.arizona.edu
  12.  
  13. In article <rfgCHyt15.Fpz@netcom.com>,
  14. Ronald F. Guilmette <rfg@netcom.com> wrote:
  15.  
  16. |Assume that I have three strings, i.e. "red ", "green ", and "blue ". Now
  17. |I want to create a generator which will successively yield each unique
  18. |string which contains no more than one instance of each of the original
  19. |strings.  Here are the string values which should be yielded by the various
  20. |invocations/resumptions of the generator:
  21. |
  22. |        ""
  23. |        "red "
  24. |        "green "
  25. |        "blue "
  26. |        "red green "
  27. |        "red blue "
  28. |        "green red "
  29. |        "green blue "
  30. |        "blue red "
  31. |        "blue green "
  32. |        "red green blue "
  33. |        "red blue green "
  34. |        "green red blue "
  35. |        "green blue red "
  36. |        "blue red green "
  37. |        "blue green red "
  38. |
  39. |After being invoked/resumed 16 times (and yielding each of the above strings
  40. |once) the generator should fail.  Note that the actual *order* in which the
  41. |above strings are yielded is totally unimportant.  Any order will do as long
  42. |as I get these 16 strings (eventually).
  43.  
  44. |Also note that the ORDER in which the original strings appear in the genera-
  45. |ted strings *is* significant.
  46.  
  47. Actually, it isn't.  You are just performing a permutation of all
  48. possible strings, so the order that the original strings appear in
  49. shouldn't matter.
  50.  
  51. Anyway, here is a piece of code to do it:
  52.  
  53.  
  54. procedure main(LArguments)
  55.  
  56.     local    SColors
  57.  
  58.     SColors := set(["red", "green", "blue" ])
  59.     every write(image(Permute(SColors)))
  60.     
  61.  
  62. end
  63.  
  64.  
  65. procedure Permute(SSet)
  66.  
  67.     local    sString
  68.  
  69.     every sString := !SSet do {
  70.         every suspend sString || " " || Permute(delete(copy(SSet), sString))
  71.     }
  72.  
  73.     return ""
  74.  
  75. end
  76.  
  77.  
  78. and it produces:
  79.  
  80. "blue red green "
  81. "blue red "
  82. "blue green red "
  83. "blue green "
  84. "blue "
  85. "red blue green "
  86. "red blue "
  87. "red green blue "
  88. "red green "
  89. "red "
  90. "green blue red "
  91. "green blue "
  92. "green red blue "
  93. "green red "
  94. "green "
  95. ""
  96.  
  97. I can't remember if I came up with this algorithm on my own or if I
  98. found it in the Icon Program Library (I can't seem to find the IPL on
  99. this machine), but I do recall posting an explanation of how this
  100. works about a year ago.  [Check the archives of the icon group mailing
  101. list / comp.lang.icon on cs.arizona.edu for more info.]
  102.  
  103. |(In practice, for
  104. |my *real* problem, the number of original strings will in fact be larger
  105. |than three... but it *will* be a fixed number (probably less that 12).
  106.  
  107. Actually, the number of strings doesn't matter.
  108. __ 
  109.     Nevin ":-)" Liber    nevin@cs.arizona.edu    (602) 293-2799
  110.                                                   ^^^ (520) after 3/95
  111. -- 
  112.     Nevin ":-)" Liber    nevin@cs.arizona.edu    (602) 293-2799
  113.                                                   ^^^ (520) after 3/95
  114.